#include <iostream>
#include <vector>
#include "lib/binary_tree.h"
using namespace std;

void convertListNode(BinaryTreeNode* cur_node, BinaryTreeNode* &pre_node) {
  if (!cur_node)
    return;
  convertListNode(cur_node->left, pre_node);

  cur_node->left = pre_node;
  if (pre_node)
    pre_node->right = cur_node;
  pre_node = cur_node;

  convertListNode(cur_node->right, pre_node);
}

BinaryTreeNode* convertToDoubleList(BinaryTreeNode* root) {
  if (!root)
    return nullptr;
  auto cur_node = root;
  BinaryTreeNode* pre_node = nullptr;
  convertListNode(cur_node, pre_node);

  auto phead = pre_node;
  while (phead->left)
    phead = phead->left;

  return phead;
}

void printBinaryTreeByList(BinaryTreeNode* root) {
  auto node = root;
  auto tail_node = root;
  std::cout << "------------------------" << std::endl;
  std::cout << "Print binary tree by list: " << std::endl;
  while (node) {
    if (!node->right) {
      tail_node = node;
    }
    std::cout << node->value << " ";
    node = node->right;
  }
  std::cout << std::endl;
  node = tail_node;
  while (node) {
    std::cout << node->value << " ";
    node = node->left;
  }
  std::cout << std::endl;
  std::cout << "------------------------" << std::endl;
}

int main() {
  vector<int> vec = {10, 6, 14, 4, 8, 12, 16};
  BinaryTreeNode* root = CreateBinaryTree(vec);
  PrintBinaryTree(root);
  auto phead = convertToDoubleList(root);
  printBinaryTreeByList(phead);

  return 0;
}
